This application contains a computer program listing submitted on CD-ROM created Aug. 30, 2002.
This invention relates to computer graphics, and in particular, to the rendering of a straight line on a display in which the voxels are arranged on a cylindrical coordinate grid.
Many computer-implemented displays consist of two-dimensional arrays of individual picture elements, or pixels. To form an image, a rasterizer selectively colors the pixels. Because the individual pixels are so small, the display appears to a human viewer to be a continuous rendering of an image. This illusion is particularly effective for complex images of continuous tones such as photographs.
For simple geometric shapes, however, the pixelated nature of the display can become apparent to the human viewer. For example, if the rasterizer is instructed to draw a straight line, there is no guarantee that the points on that desired line will coincide with the pixels that are available for rendering the line. As a result, the desired line is often rendered by a rasterized line of pixels that are close to but not necessarily coincident with the desired line. This results in rasterized lines that have a jagged or echeloned appearance.
In the course of rendering an image, a large number of straight lines and line segments are often drawn. As a result, given a desired line, the rasterizer must frequently select those pixels that will minimize the jagged appearance of the resulting rasterized line. A straightforward mathematical approach is to use the equation of the desired line and the coordinates of the available pixels to minimize a least square error across all points on the line. While such an approach has the advantage of globally optimizing the selection of pixels on the rasterized line, the large number of floating point operations required causes this approach to be prohibitively time-consuming.
To meet constraints on speed, rasterizers typically implement rasterization methods that avoid time-consuming floating point operations. Among the methods that meet the foregoing constraints is that taught in Bresenham, J. E., xe2x80x9cAlgorithm for Computer Control of a Digital Plotter,xe2x80x9d IBM System Journal, Vol. 4, pp. 25-30, 1965, the contents of which are herein incorporated by reference. Using only integer operations, the Bresenham algorithm reduces the choice of what pixel to select to an examination of the sign of a discriminant.
Even faster rasterization methods exist that select multiple points on the rasterized line based on the outcome of a single decision. There also exist a variety of rasterization methods aimed at rendering conic sections and quadric sections on a pixelated display.
However, the foregoing rasterization methods all rely on the assumption that the array of pixels is arranged in a uniform rectangular grid that can readily be modeled by a Cartesian coordinate system. This is a reasonable assumption given the prevalence of two-dimensional displays such as computer monitors and printers at the time these algorithms were developed.
Since then, however, volumetric, or three-dimensional displays have been developed. Such displays permit the generation, absorption, or scattering of visible radiation from a set of localized and specified regions within a volume. Examples of such systems are taught in Hirsch U.S. Pat. No. 2,967,905, Ketchpel U.S. Pat. No. 3,140,415, Tsao U.S. Pat. No. 5,754,147 and on pages 66-67 of Aviation Week, Oct. 31, 1960.
In a typical volumetric display 1, shown in FIG. 1, a motor 2 spins an imaging plate 3 rapidly about an axis 4. A light source 5 under the control of a rasterizer 6 illuminates selected spots 7 on the imaging plate 3 at successive instants. If the imaging plate 3 spins rapidly enough, and if the successive instants are separated by short enough time intervals, a continuous curve will appear to hang in mid-air.
FIG. 2 illustrates the projection 8 onto a plane perpendicular to the axis 4 of an exemplary line rendered by the rasterizer 6. In FIG. 2, the imaging plate 3 is shown in six successive instants as it rotates around the axis 4, now perpendicular to the page. At each of the six instants, the light source 5, under the control of the rasterizer 6, illuminates a spot 7 on the imaging plate 3. As shown in FIG. 2, by aiming the light source 5 at the correct spot and firing the light source 5 at the right time, it is possible to trace out the line. It is the function of the rasterizer 6 to correctly aim and fire the light source 5 so as to trace out the line.
To aim the light source 5, the rasterizer 6 needs a way to identify points in space. In other words, the rasterizer 6 needs a coordinate system. One possible coordinate system is a Cartesian coordinate system.
Using a Cartesian coordinate system, the rasterizer 6 would draw the line 8 in FIG. 2 by specifying, for example, that at time t1, the light-source 5 should aim 30 units north, at time t2, the light-source 5 should aim 29 units north, 1 unit east and 1 unit in elevation, at time t3, the light-source 5 should aim 28 units north, 2 units east and 2 units in elevation, and so on. To ensure that the imaging plate 3 is at the appropriate location, the rasterizer 6 also has to specify the values of the times t1, t2 and t3 based on how fast the imaging plate 3 is spinning. Although the spinning of the imaging plate 3 can be resolved into a north-south component and an east-west component, this is a computationally taxing exercise that can easily be avoided by using a polar coordinate system.
As an alternative, the rasterizer 6 could draw the line in FIG. 2 in cylindrical coordinates by specifying, for example, that at time t1, the light source 5 should aim 30 units away from the axis 4 at a 90 degree angle, at time t2, the light source 5 should aim 29.02 units from the axis 4 at an angle of 88.03 degrees and point up by 1 unit of elevation, and at time t3, the light source 5 should aim at 28.07 units from the axis 4 at an angle of 85.91 degrees and point up by 2 units of elevation. This would, of course, draw the same line that was drawn using Cartesian coordinates. The advantage of using cylindrical coordinates becomes apparent when it comes time to specify when to fire the light source 5. Because the imaging plate 3 is spinning, it is far more natural to represent its motion in terms of degrees per second than it is to resolve its motion into a north-south component and an east-west component. For this reason, calculations involving motion of the imaging plate 3 in a volumetric display are best performed in terms of a cylindrical coordinate system.
The process of rendering a line in a cylindrical coordinate system is fundamentally different from that of rendering a line in a Cartesian coordinate system. In a Cartesian coordinate system, a line has a constant slope. A unit change in one direction always results in the same change in the remaining two directions, regardless of where that change occurs. This is not the case in a cylindrical coordinate system.
In a cylindrical coordinate system, the slope of a line can vary dramatically with position along the line. In contrast to a Cartesian coordinate system in which the slope of a line is constant at all points on the line, the slope of a line in a cylindrical coordinate system can vary significantly along the line. This is because the coordinate grid in a cylindrical coordinate system is not a spatially uniform grid, as is the coordinate grid in a Cartesian coordinate system.
For those portions of the line that are closest to the axis of the cylindrical coordinate system, the change in distance of the line from the origin changes very slowly with angle. For those portions of the line that are far from the axis of the cylindrical coordinate system, even a small change in angle results in a huge change in radial distance from the axis.
A rasterizer according to the invention recognizes that the dominant direction of a desired line in a cylindrical coordinate system changes in a predictable manner. The rasterizer uses this predictable sequence of dominant directions, referred to as a xe2x80x9cdominance progression,xe2x80x9d to avoid having to determine the dominant direction at each point on the desired line before rendering a voxel representative of that point. Instead, the rasterizer detects boundaries between constituent line-segments of the desired line and uses the dominance progression to determine the dominant direction of the line at any point. Because the process of detecting a transition between boundaries is much faster than that of evaluating a dominant direction, a rasterizer practicing the method of the invention can rapidly and efficiently draw a rasterized line in a cylindrical coordinate system.
The rasterizer renders, on a volumetric display, a rasterized line that approximates a desired line. It does so by rendering, on the volumetric display, a first voxel representative of a first point from the desired line. The first point is selected from a first constituent line-segment having a first dominant direction. Then, the rasterizer selects a second point from the desired line and determines whether that second point is on a second constituent line-segment, with a second dominant direction, or whether that second point is on the same constituent line segment.
On the basis of this determination, the rasterizer renders a second voxel representative of the second point on the desired line. This second voxel is located so as to minimize a distance between the second voxel and the second point on the desired line. The second voxel can be selected, for example, by application of a midpoint method to select the second voxel from a plurality of candidate voxels.
In one practice of the invention, the rasterizer evaluates a difference between a threshold and a transition-indicating expression evaluated at the second point. This difference is indicative of a transition from the first constituent line-segment to the second constituent line-segment. The transition indicating-expression is typically an expression whose value depends on a slope of the desired line at the second point. The slope can be defined as a ratio of how much the desired line changes in the first dominant direction with respect to a change in one of two non-dominant directions.
In some cases, the orientation of the line to be rasterized is such that the transition cannot be reliably detected. This occurs, in part, because of computation on a digital computer cannot be carried out with infinite precision. In one practice of the invention, erroneous transitions are avoided by selecting the transition-indicating expression to be one that identifies a line having a point at which the slope is equal to the threshold.
Unless otherwise defined, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of the present invention, suitable methods and materials are described below. All publications, patent applications, patents, and other references mentioned herein are incorporated by reference in their entirety. In case of conflict, the present specification, including definitions, will control. In addition, the materials, methods, and examples are illustrative only and not intended to be limiting.
Other features and advantages of the invention will be apparent from the following detailed description, and from the claims.